#include<iostream>
#include<vector>

using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		if (!head) return NULL;
		vector<ListNode *> list;
		ListNode *loop = NULL;
		while (head) {
			for (int i = 0; i < list.size(); i++) {
				if (list[i] == head->next) 
					return head->next;				
			}
			list.push_back(head);
			head = head->next;
		}
		return loop;
	}
};

void main() {
	Solution s;
	ListNode n3(3), n2(2), n0(0), n_4(-4);
	n3.next = &n2, n2.next = &n0,n0.next=&n_4,n_4.next=&n2;
	s.detectCycle(&n3);
}